home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HyperLib 1997 Winter - Disc 1
/
HYPERLIB-1997-Winter-CD1.ISO.7z
/
HYPERLIB-1997-Winter-CD1.ISO
/
オンラインウェア
/
BUS
/
XSortLab.sit
/
xSortLab
/
About xSortLab
next >
Wrap
Text File
|
1995-05-31
|
6KB
|
116 lines
June 1, 1995
David Eck
Department of Mathematics and Computer Science
Hobart and William Smith Colleges
Geneva, NY 14456 USA
E-mail: eck@hws.edu
WWW: http://hws3.hws.edu:9000/eck/index.html
xSortLab is a program for learning about and experimenting with five
sorting algorithms: bubble sort, selection sort, insertion sort,
merge sort and quicksort. The program has two modes of operation,
visual and timed. In visual mode, sixteen bars are sorted,
step-by-step, according to size. In timed mode, lists of numbers
are sorted and the computer reports how long the sort took.
The program is easy to use; instructions are given below.
I wrote this program, and several others, for use with my
introductory computer science textbook: _The Most Complex Machine:
A Survey of Computers and Computing_ (AK Peters Ltd, Wellesley, MA,
ISBN number 1-56881-054-7), to be published in July of 1995. You
should find an order form for this book in the folder containing
the program (just in case you are interested). You can find
information about the book and other programs on the World Wide Web
at this URL:
http://math.hws.edu/TMCM.html
COPYRIGHT RESTRICTIONS: xSortLab can be freely distributed for
private, non-commercial use. I stipulate, however, that this
material should not be adopted for use in a course unless the book
_The Most Complex Machine_ is also adopted. This material can be
included on inexpensive CD-ROM shareware collections. It can be
made available for downloading from FTP sites and on-line services,
provided that no charge is made beyond such basic charges as
connect time and membership fee.
------------------------------------------------------------------------
Using xSortLab:
--------------
xSortLab has two windows. The "Sort Window" is used, along with the
menus, for overall control of the program. The Sort Window is visible
when the program first starts up. The "Log Window" displays statistics
on sorts done by the program. It is initially behind the Sort Window.
There are commands in the File Menu for printing the data in the Log
Window to a file and for saving the data to a file.
My recommended method for using xSortLab is to
1) Start it up, and choose a sorting method from the Method
Menu. You will see 16 bars lined up in random order, waiting
to be sorted.
2) Click repeatedly on the Next button (or press Command-;) to
work through the sort one step at a time. A message describing
each step will be displayed at the bottom of the window. The
object here is to understand exactly how the sort works. The
New Sort button can be used to randomize the order of the bars
and start over.
3) Then, try the Go button to let the computer do the sort
automatically, while you watch. The object here is to get
a better overall view of the process. This automatic sorting
can be done at two speeds. You can control the speed by
selecting either "Visual/Fast" or "Visual/Slow" from the
Speed Menu.
4) Use the other two entries in the Speed Menu -- Timed/Uninterruptable
and Timed/Interruptable -- to gather statistics about the sort.
The statistics are reported in the Log Window. The Timed/Interruptable
speed is useful for counting comparison and copy operations; it
also reports how long the sorting took, but most of this time is
overhead, so it should not be taken too seriously. The
Timed/Uniterruptable sort reports only how long the process took.
This is the actual processing time required by your computer to
do the sorting. A Timed/Uniterruptable sort is, in fact,
uninterruptable, except by aborting the program with Command-
Option-Escape or by restarting the computer.
Notes:
-- Time is measured in "ticks". Each tick is equal to 1/60 second.
At computer speeds, this is a lot of time, and you will find that
the time reported for sorting a single small array is zero. To get
a more accurate time, you should sort a large number of arrays of
the same size, and divide by the number of arrays. When you use
the Timed/Interruptable or Timed/Uninterruptable sorting procedure,
two input boxes appear where you can type in the number of
arrays as well as the size of each array. (Keeping track of
multiple arrays does add a certain amount of overhead to the
processing time, but except for very large numbers of small
arrays, it is negligible. If you really want to be accurate,
you could try measuring the overhead by "sorting" a large number
of arrays of size 1.)
-- The Method Menu is used to select one of five sorting methods.
If you select a new method while a "visual" sort is in progress,
the sort in progress will continue using the old method. The
new method will come into effect the next time you start a
new sort. The sort method that is actually in use at any given time
is displayed in the title bar of the Sort Window.
-- The Control Menu contains commands that duplicate the functions of
the buttons in the Sort Window. It also has commands for bringing
the Sort Window and the Log Window to the front and for clearing
the Log Window.
-- The program's default memory allocation is set so that it can operate
on up to 200,000 items. However, it can actually operate on up to
1,000,000 items if you increase the memory allocation.